package com.buddy.algorithm.list;

import java.util.Scanner;

/**
 * 链表结构
 */
public class ChainList {
    public static void main(String[] args) {
        CLType node, head = null;
        CLType clType = new CLType();
        String key, findKey;
        Scanner input = new Scanner(System.in);
        System.out.println("链表测试，请输入链表数据，格式为：key name age");
        do {
            Data nodeData = new Data();
            nodeData.key = input.next();
            if (nodeData.key.equals("0")) {
                break;
            } else {
                nodeData.name = input.next();
                nodeData.age = input.next();
                head = clType.addEnd(head, nodeData);
            }
        } while (true);
        clType.allNode(head);//显示所有节点

        System.out.println("演示插入结点，输入插入位置的key：");
        findKey = input.next();
        System.out.println("输入待插入结点的数据(key name age):");
        Data nodeData = new Data();
        nodeData.key = input.next();
        nodeData.name = input.next();
        nodeData.age = input.next();
        head = clType.insertNode(head,findKey,nodeData);
        clType.allNode(head);
        System.out.println("演示插入结点结束！");

        System.out.println("演示删除结点，输入要删除的key：");
        key = input.next();
        clType.deleteNode(head,key);
        clType.allNode(head);
        System.out.println("演示删除结点结束！");

        System.out.println("演示在链表中查找，输入要查找的key：");
        key = input.next();
        node = clType.findNode(head,key);
        if (node != null){
            nodeData = node.nodeData;
            System.out.println("查找出来的结果为：{key:"+nodeData.key+",name:"+nodeData.name+",age"+nodeData.age+"}");
        }else {
            System.out.println("在链表中未找到key");
        }

    }
}


/**
 * 数据元素
 */
class Data {
    String key;//结点关键字
    String name;
    String age;
}

/**
 * 定义链表结构
 */
class CLType {
    Data nodeData = new Data();
    CLType nextNode;//指向下一个节点

    /**
     * 追加节点
     * 1.分配内存空间，保存新增的节点，下一个节点结点置为空；
     * 2.从头引用head开始逐个检查，直到找到最后一个结点
     * 3.将表尾结点的地址部分设置为新增结点的地址
     * 4.将新增结点的地址部分设置为null，即新增节点为表尾
     *
     * @param head     链表头引用
     * @param nodeData 要追加的节点
     * @return 返回头引用
     */
    CLType addEnd(CLType head, Data nodeData) {
        CLType node, htemp;
        if ((node = new CLType()) == null) {
            System.out.println("申请内存失败！");
            return null;
        } else {
            node.nodeData = nodeData;
            node.nextNode = null;
            if (head == null) {
                head = node;
                return head;
            }
            htemp = head;
            while (htemp.nextNode != null) {
                htemp = htemp.nextNode;
            }
            htemp.nextNode = node;
            return head;//head和htemp地址值是一样的，因此修改其中任何一个，两个同时发生变化
        }
    }

    /**
     * 插入头节点
     * 1.分配内存空间，保存新结点；
     * 2.使新增结点指向头引用head所指向的节点
     * 3.使头引用head指向新增结点
     *
     * @param head     链表头引用
     * @param nodeData 待插入的新结点
     * @return 返回头引用
     */
    CLType addFirst(CLType head, Data nodeData) {
        CLType node;
        if ((node = new CLType()) == null) {
            System.out.println("申请内存失败！");
            return null;
        } else {
            node.nodeData = nodeData;
            node.nextNode = head;
            head = node;
            return head;
        }
    }

    /**
     * 插入结点
     *
     * @param head     头引用
     * @param findKey  key 要插入的结点在其后面
     * @param nodeData 要插入的数据
     * @return 返回头引用
     */
    CLType insertNode(CLType head, String findKey, Data nodeData) {
        CLType node, nodeTemp;
        if ((node = new CLType()) == null) {
            System.out.println("分配内存空间失败！");
            return null;
        }
        node.nodeData = nodeData;
        nodeTemp = findNode(head, findKey);
        if (nodeTemp != null) {
            node.nextNode = nodeTemp.nextNode;
            nodeTemp.nextNode = node;
        } else {
            System.out.println("未找打正确的插入位置！");
        }

        return head;
    }

    /**
     * 查找结点
     *
     * @param head 链表头引用
     * @param key  键
     * @return 查找到的节点
     */
    CLType findNode(CLType head, String key) {
        CLType htemp;
        htemp = head;
        while (htemp != null) {
            if (htemp.nodeData.key.compareTo(key) == 0) {
                return htemp;
            }
            htemp = htemp.nextNode;
        }
        return null;
    }

    /**
     * 1.查找需要删除的结点
     * 2.使前一结点指向当前结点的下一结点
     * 3.删除结点
     *
     * @param head
     * @param key
     * @return
     */
    int deleteNode(CLType head, String key) {
        CLType node, htemp;
        htemp = head;
        node = head;
        while (htemp != null) {
            if (htemp.nodeData.key.compareTo(key) == 0) {
                node.nextNode = htemp.nextNode;
                htemp = null;
                return 1;
            } else {
                node = htemp;
                htemp = htemp.nextNode;
            }
        }
        return 0;
    }

    /**
     * 计算链表长度
     *
     * @param head 链表头引用
     * @return
     */
    int length(CLType head) {
        CLType htemp;
        int len = 0;
        htemp = head;
        while (htemp != null) {
            len++;
            htemp = htemp.nextNode;
        }
        return len;
    }

    void allNode(CLType head) {
        CLType htemp;
        Data nodeData;
        htemp = head;
        while (htemp != null) {
            nodeData = htemp.nodeData;
            System.out.println("{key:" + nodeData.key + ",name:" + nodeData.name + ",age:" + nodeData.age + "}");
            htemp = htemp.nextNode;
        }
    }
}